class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        if (preorder.size() == 0) return NULL;
        int pos = 0, n = preorder.size();
        while (inorder[pos] != preorder[0]) pos += 1;
        TreeNode *root = new TreeNode(preorder[0]);
        vector<int> preArr, inArr;
        for (int i = 1; i <= pos; i++) preArr.emplace_back(preorder[i]);
        for (int i = 0; i < pos; i++) inArr.emplace_back(inorder[i]);
        root->left = buildTree(preArr, inArr);
        preArr.clear();
        inArr.clear();
        for (int i = pos + 1; i < n; i++) preArr.emplace_back(preorder[i]);
        for (int i = pos + 1; i < n; i++) inArr.emplace_back(inorder[i]);
        root->right = buildTree(preArr, inArr);
        return root;
    }
    // iteration method
    // TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
    //    if (preorder.size()== 0) return NULL;
    //     TreeNode* root = new TreeNode(preorder[0]);
    //     stack<TreeNode*> stk;
    //     stk.push(root);
    //     int inorderIndex = 0;
    //     for (int i = 1; i < preorder.size(); ++i) {
    //         int preorderVal = preorder[i];
    //         TreeNode* node = stk.top();
    //         if (node->val != inorder[inorderIndex]) {
    //             node->left = new TreeNode(preorderVal);
    //             stk.push(node->left);
    //         }
    //         else {
    //             while (!stk.empty() && stk.top()->val == inorder[inorderIndex]) {
    //                 node = stk.top();
    //                 stk.pop();
    //                 ++inorderIndex;
    //             }
    //             node->right = new TreeNode(preorderVal);
    //             stk.push(node->right);
    //         }
    //     }
    //     return root;
    // }
};